/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann - Tübingen, Germany 
 * Niko Schenk - Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package saphre.core;

import java.io.Serializable;
import java.util.*;
import util.sorting.RadixQSort;
import util.sorting.RevRadixQSort;
import util.tokenization_io.TokenIterator;
import util.tokenization_io.Tokenizer;
import util.sedgewick.Stopwatch;
import util.tokenization_io.BoundarySymbols;
import collectors.impl.CollectLevelIntervals;
import util.sorting.SkewSort;
import collectors.impl.visitors.CollectTraversal;
import util.Interval;
import util.IntervalLink;
import util.LinkedInterval;
import util.Rev;

/**
 * Implementation of:
 *
 * Linearised Suffix Tree (Kim et al. 2008)
 *
 * #64;article{lst, Author = {Dong Kyue Kim and Minhwan Kim and Heejin Park},
 * Title = {Linearized Suffix Tree: an Efficient Index Data Structure with the
 * Capabilities of Suffix Trees and Suffix Arrays}, Journal = {Algorithmica},
 * Volume = 52, Number = 3, Pages = {350--377}, Year = 2008 }
 *
 * @author Dale Gerdemann
 * modified by Niko Schenk
 */
public class SuffixArray implements Serializable {

    // A Store object holds the (corpus) text data,
    // as well as information about tokenization and boundaries
    // and keeps integer representations of all the words.
    // TODO: remove static modifier.
    public static Store store; 
    // The boundary symbols.
    public static BoundarySymbols tc;
    public static int[] suftab1;
    public int N;
    public Interval top;
    int alphaSize; // Size of alphabet rounded up to next power of 2.
    // Used for construction of new child table.
    // Several tables. All using 1-based indexing for conformity with
    // Kim et al. See lst/Array1.java.
    public int[] text;    // The text is a sequence of int, presumably created
    // by a tokenizer.
    public int[] suftab;  // suffix table, analogous to the
    // Enhanced Suffix Array (Abouelhoda et al. 2004) 
    // "pos" in Kim et al.
    // int[] savedSuftab;  // backup
    public int[] lcptab;  // longest common prefix table
    // int[] savedLcptab;  // backup
    int[] bwttab;  // Burrows-Wheeler transform, discussed in Abouelhoda
    //  et al. Useful to extract "maximal" and "supermaximal" repeats
    // New and old child table. First as in Abouelhoda et al and
    // then used to get the extended lcp (which includes depth),
    // and then with this extlcp, cldtab is recalculated in the
    // new way as in Kim et al.
    public int[] cldtab;  // Child table
    // int[] savedCldtab;  // backup
    public boolean isPrefixArray = false;
    Interval[] lnktab;

    // Constructor flags
    public enum FLAG {

        TIMING, NO_CHILD_TABLE, MINIMAL
    }

    /**
     * SuffixArray constructor
     * Generates all suffix array components (suftab, lcptab, bwtab, etc.)
     * based on a Store object.
     *
     * @param text the tokenized text with int's substituted for tokens
     * @param alphaSize the size of the alphabet. May be quite large, as this
     * implementation is specialized for large alphabets.
     */
    public SuffixArray(Store store) {
        // Assume your corpus (text) looks like this.
        // mining_engineering
        //
        // 1. The algorithm appends a (unique) "$" to the beginning,
        // and two (distinct) "$" symbols to the end.
        // The new text looks like this:
        // $mining_engineering$$
        // 
        // A second step consists of mapping each character 
        // (including the question mark sentinels) to a unique index.
        // Like this:
        // $=0, m=1, i=2, ..3456789........18=g,19=$,20=$

        // Again:
        // mining_engineering    <- original lexicographic.
        // $mining_engineering$$  <- original with sentinels.
        // 1234567891011121314151617181920 <- original indices with sentinels.

        // A third step consists of sorting the indices in lexicographic order:
        // eeegggiiiimnnnnnr_     <- help sorted lexicographic.
        // 000111222234444456     <- help sorted transcribed.
        // 324241634124005241     <- lexicographic, transcribed.

        // 9 324241604124005241 7 8 <- original with end markers!
        // Note: endmarkers 7,8,9 are distinct!

        // The lexicographically sorted indexes
        // resulting in the SUFFIX ARRAY look like this:

        // 0 13 8 14 10 6 18 11 4 16 2 1 12 9 5 17 3 15 7 19 20
        //   

        // lexicogaphically sorted.         lcp
        // 0  - ^mingin_engineering         0 ???
        // 13 - eering$                     -1
        // 8  - engineering$                1
        // 14 - ering$                      1
        // 10 - gineering$                  0
        // 6  - g_engineering$              1
        // 18 - g$                          1
        // 11 - ineering$                   0
        // 4  - ing_engineering$            2
        // ...                              ..

        // ..                               ..
        // 15 - ring
        // 7 - _engineering
        // 19



        // int[] corN = {4, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 3};
        // corresponds to 
        // $mining_engineering$$

        // The lexicographically sorted suffixes.
        // 0 13 8 14 10 6 18 11 4 16 2 1 12 9 5 17 3 15 7 19 20


        // lcptab: 0 -1 1 1 0 1 1 0 2 3 2 0 0 1 2 2 1 0 0 0 0 

        // cldtab: 0 4 3 2 7 6 5 11 10 9 8 12 17 16 15 14 13 18 19 20 1 
        //              [0, 20]
        //  ------------
        //  |          | 
        //  [1,3]     [


        System.out.println("\n\nGenerating Suffix Array...");
        this.text = store.text;
        tc = store.getTC();
        this.store = store;
        N = text.length - 2;
        top = new Interval(1, N);
        this.alphaSize = (int) Math.pow(2, ceillog(store.alphaSize()));

        Stopwatch sw = new Stopwatch();
        Stopwatch swsuftab = new Stopwatch();
        System.out.print("Generating suftab...\t");
        suftab = getSuftab(text);

//        System.out.println("Suffixes:");
//        for(int idx : suftab) {
//            for(int start = idx; start < text.length; start++) {
//                System.out.print(text[start] + " ");
//            }
//            System.out.println();
//        }
        //  System.out.print("suftab: "); for(int i : suftab) { System.out.print(i + " "); } System.out.println();
        System.out.println("... finished generating suftab in\t" + swsuftab.elapsedTime() + " seconds.");
       
        suftab1 = suftab;
        System.out.print("Generating lcptab...\t");
        Stopwatch swlcptab = new Stopwatch();
        lcptab = SuffixArray.getLcptab(suftab, text);
        //1  System.out.print("lcptab: "); for(int i : lcptab) { System.out.print(i + " "); } System.out.println();
        System.out.println("... finished generating lcptab in\t" + swlcptab.elapsedTime() + " seconds.");
        
        // bwttab = SuffixArray.getBwttab(suftab, text);
        System.out.print("Generating childtab...\t");
        Stopwatch swchldtab = new Stopwatch();
        cldtab = SuffixArray.getChildtab(lcptab);
        //1 System.out.print("cldtab: "); for(int i : cldtab) { System.out.print(i + " "); } System.out.println();
        System.out.println("... finished generating chldtab in\t" + swchldtab.elapsedTime() + " seconds.");
        
        System.out.print("Generating extlcptab...\t");
        Stopwatch swextlcp = new Stopwatch();
        int[] extlcp = SuffixArray.getExtlcp(this.alphaSize, cldtab, lcptab);
        cldtab = SuffixArray.getChildtab(extlcp);
        //1  System.out.print("newcldtab: "); for(int i : cldtab) { System.out.print(i + " "); } System.out.println();
        System.out.println("... finished generating extlcpdtab in\t" + swextlcp.elapsedTime() + " seconds.");
        
        System.out.println("The whole procedrue took: " + sw.elapsedTime() + " seconds.\n");
        System.out.println();
    }

    /**
     * The SuffixArray Constructor with timing info or with no child table
     *
     * @param text the tokenized text with int's substituted for tokens
     * @param alphaSize the size of the alphabet. May be quite large, as this
     * implementation is specialized for large alphabets.
     * @param flag used to distinguish this construuctor
     */
    public SuffixArray(int[] text, int alphaSize, FLAG flag) {
        tc = store.getTC();
        if (flag == FLAG.TIMING) {
            Stopwatch stop = new Stopwatch();
            this.text = text;
            N = text.length - 1;
            top = new Interval(1, N);

            this.alphaSize = (int) Math.pow(2, ceillog(alphaSize));

            suftab = getSuftab(text);
            System.out.println("Time for sorting suffixes: "
                    + stop.elapsedTime());
            stop = new Stopwatch();
            lcptab = SuffixArray.getLcptab(suftab, text);
            System.out.println("Time for lcp table: " + stop.elapsedTime());
            stop = new Stopwatch();
            cldtab = SuffixArray.getChildtab(lcptab);
            System.out.println("Time for initial child table: "
                    + stop.elapsedTime());
            stop = new Stopwatch();
            int[] extlcp =
                    SuffixArray.getExtlcp(this.alphaSize, cldtab, lcptab);
            System.out.println("Time for extended lcp table: "
                    + stop.elapsedTime());
            stop = new Stopwatch();
            cldtab = SuffixArray.getChildtab(extlcp);
            System.out.println("Time for new child table: "
                    + stop.elapsedTime());

        } else if (flag == FLAG.NO_CHILD_TABLE) {
            this.text = text;
            this.alphaSize = (int) Math.pow(2, ceillog(alphaSize));
            suftab = getSuftab(text);
            tc = store.getTC();
            lcptab = SuffixArray.getLcptab(suftab, text);
        } else if (flag == FLAG.MINIMAL) {
            this.text = text;
            this.alphaSize = (int) Math.pow(2, ceillog(alphaSize));
        }
    }

    /**
     * Special constructor to make a SuffixArray for a subset of suffixes.
     *
     * @param sa a normal SuffixArray for the same text
     * @param suftab a sorted array of a subset of suffixes of the text
     */
    public SuffixArray(SuffixArray sa, int[] suftab) {
        this.text = sa.text;
        this.N = sa.N;
        this.top = sa.top;
        this.alphaSize = sa.alphaSize;
        this.suftab = suftab;
        tc = store.getTC();
        lcptab = SuffixArray.getLcptab(suftab, text);
        cldtab = SuffixArray.getChildtab(lcptab);
        int[] extlcp = SuffixArray.getExtlcp(this.alphaSize, cldtab, lcptab);
        cldtab = SuffixArray.getChildtab(extlcp);
    }

    /**
     * Special constructor to make a "SuffixArray" that actually encodes a
     * prefix array. The methods are the same, so it makes sense to reuse the
     * SuffixArray class for this purpose.
     *
     * @param sa a normal SuffixArray for the same text
     * @param prefixTable a sorted array of prefixes of the text
     * @param lcstab longest common suffix table
     */
    public SuffixArray(SuffixArray sa, int[] prefixTable, int[] lcstab) {
        isPrefixArray = true;
        this.text = sa.text;
        N = text.length - 1;
        top = new Interval(1, N);
        this.alphaSize = sa.alphaSize;
        this.suftab = prefixTable;
        this.lcptab = lcstab;
        cldtab = SuffixArray.getChildtab(lcstab);
        int[] extlcp = SuffixArray.getExtlcp(this.alphaSize, cldtab, lcstab);
        cldtab = SuffixArray.getChildtab(extlcp);
    }

    /**
     *
     * @param store
     */
    public void setStore(Store store) {
        this.store = store;
    }

    /**
     *
     * @return
     */
    public SuffixArray prefixArray() {

        int N = store.text.length - 1;
        int[] preftab = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            preftab[i] = i - 1;
        }

        RevRadixQSort rv = new RevRadixQSort(store.text);
        rv.sort(preftab, 1, N, 0);

        int[] lcptab2 = Rev.getLcstab(preftab, store.text, store.getTC());
        return new SuffixArray(this, preftab, lcptab2);
    }

    public int[] psi() {
        int[] result = new int[suftab.length];
        for (int i = 0; i < result.length; i++) {
            result[suftab[i]] = i;
        }
        return result;
    }

    /**
     * @param pat the pattern to look for
     * @param inter the Interval in which to look.
     * @return the Interval where the pattern is found. A search miss returns a
     * null interval. See the <code>before</code> and <code>after</code> methods
     * in {@link Interval}.
     */
    public Interval search(int[] pat, Interval inter) {
        return search(pat, 0, inter);
    }

    public Interval searchUni(int id) {
        int[] pat = new int[1];
        pat[0] = id;
        return search(pat, 0, top);
    }

    public Interval searchBi(int id1, int id2) {
        int[] pat = new int[2];
        pat[0] = id1;
        pat[1] = id2;
        return search(pat, 0, top);
    }

    public Interval searchTri(int id1, int id2, int id3) {
        int[] pat = new int[3];
        pat[0] = id1;
        pat[1] = id2;
        pat[2] = id3;
        return search(pat, 0, top);
    }

    /**
     * @param patternString the pattern to look for in top interval
     * @return the Interval where the pattern is found. A search miss returns a
     * null interval. See the <code>before</code> and <code>after</code> methods
     * in {@link Interval}.
     */
    public Interval search(String patternString, Store store) {
        Tokenizer tok = store.getTokenizer();
        List<String> tokseq = new ArrayList<String>();
        TokenIterator iter = tok.iterator(patternString);
        while (iter.hasNext()) {
            tokseq.add(iter.next());
        }
        int[] pattern = new int[tokseq.size()];
        for (int i = 0; i < pattern.length; i++) {
            String saved = tokseq.get(i);
            pattern[i] = store.wordToIntChecked(saved);
        }
        return search(pattern, 0, top);
    }

    /**
     * @param pat the pattern to look for in top interval
     * @return the Interval where the pattern is found. A search miss returns a
     * null interval. See the <code>before</code> and <code>after</code> methods
     * in {@link Interval}.
     */
    public Interval search(int[] pat) {
        return search(pat, 0, top);
    }

    private Interval search(int[] pat, int i, Interval inter) {
        if (inter.trivial()) {
            int p = suftab[inter.lb()];
            for (; i < pat.length && p + i < text.length; i++) {
                int c = text[p + i];
                //System.out.println("Comparing " + pat[i] + " with " + c);
                if (pat[i] < c) {
                    return inter.before();
                } else if (pat[i] > c) {
                    return inter.after();
                }
            }
            return inter;
        }

        // Get child boundary
        int mid = cldtab[inter.lb()];
        if (mid <= inter.lb() || mid > inter.rb()) {
            mid = cldtab[inter.rb()];
        }

        // Consume pattern up to the next lcp level. For non-leaves,
        // nothing happens here.

        for (; i < lcptab[mid] && i < pat.length; i++) {
            int c = text[suftab[mid] + i];
            if (pat[i] < c) {
                return inter.before();
            } else if (pat[i] > c) {
                return inter.after();
            }
        }

        // After consuming from pattern, check to see if any remaining
        if (i == pat.length) {
            return inter;
        }

        // Decide left or right subtree
        Interval inter1;
        if (pat[i] < text[suftab[mid] + i]) {
            inter1 = new Interval(inter.lb(), mid - 1);
        } else {
            inter1 = new Interval(mid, inter.rb());
        }

        return search(pat, i, inter1);
    }

    public List<Interval> searchPath(int[] pat, Interval inter) {
        List<Interval> result = new ArrayList<Interval>();
        result.add(inter);
        searchPath(pat, 0, inter, result);
        return result;
    }

    public void searchPath(int[] pat, int i, Interval inter,
            List<Interval> result) {
        if (inter.trivial()) {
            int p = suftab[inter.lb()];
            for (; i < pat.length && p + i < text.length; i++) {
                int c = text[p + i];
                // System.out.println("Comparing " + pat[i] + " with " + c);
                if (pat[i] < c) {
                    result.add(inter.before());
                    return;
                } else if (pat[i] > c) {
                    result.add(inter.after());
                    return;
                }
            }
            result.add(inter);
            return;
        }


        // Get child boundary
        int mid = cldtab[inter.lb()];
        if (mid <= inter.lb() || mid > inter.rb()) {
            mid = cldtab[inter.rb()];
        }

        // Consume pattern up to the next lcp level. For non-leaves,
        // nothing happens here.
        int level = i;
        for (; i < lcptab[mid] && i < pat.length; i++) {
            int c = text[suftab[mid] + i];
            if (pat[i] < c) {
                result.add(inter.before());
                return;
            } else if (pat[i] > c) {
                result.add(inter.after());
                return;
            }
        }

        if (level != i) {
            result.add(inter);
        }

        // After consuming from pattern, check to see if any remaining
        if (i == pat.length) {
            return;
        }

        // Decide left or right subtree
        Interval inter1;
        if (pat[i] < text[suftab[mid] + i]) {
            inter1 = new Interval(inter.lb(), mid - 1);
        } else {
            inter1 = new Interval(mid, inter.rb());
        }

        searchPath(pat, i, inter1, result);
    }

    public Interval searchPenult(int[] pat, Interval inter) {
        Interval prev = new Interval(0, -1);
        return search(pat, 0, inter, prev);
    }

    public Interval search(int[] pat, int i, Interval inter, Interval prev) {
        if (inter.trivial()) {
            int p = suftab[inter.lb()];
            for (; i < pat.length && p + i < text.length; i++) {
                int c = text[p + i];
                // System.out.println("Comparing " + pat[i] + " with " + c);
                if (pat[i] < c) {
                    return prev;
                } else if (pat[i] > c) {
                    return prev;
                }
            }
            return prev;
        }

        // Get child boundary
        int mid = cldtab[inter.lb()];
        if (mid <= inter.lb() || mid > inter.rb()) {
            mid = cldtab[inter.rb()];
        }

        // Consume pattern up to the next lcp level. For non-leaves,
        // nothing happens here.
        for (; i < lcptab[mid] && i < pat.length; i++) {
            int c = text[suftab[mid] + i];
            if (pat[i] < c) {
                return prev;
            } else if (pat[i] > c) {
                return prev;
            }
        }

        // After consuming from pattern, check to see if any remaining
        if (i == pat.length) {
            return prev;
        }

        // Decide left or right subtree
        Interval inter1;
        if (pat[i] < text[suftab[mid] + i]) {
            inter1 = new Interval(inter.lb(), mid - 1);
        } else {
            inter1 = new Interval(mid, inter.rb());
        }

        return search(pat, i, inter1, inter);
    }

    public static int[] maximize(int[] pat, Interval inter,
            SuffixArray sa, SuffixArray pa,
            Store store) {
        Interval found = pa.revSearch(pat, inter);
        int lcp = pa.getLcp(found);
        int loc = pa.suftab[found.lb()];
        int[] pat1 = store.toArray(loc - lcp + 1, loc + 1);
        found = sa.search(pat1, inter);
        lcp = sa.getLcp(found);
        loc = sa.suftab[found.lb()];
        pat1 = store.toArray(loc, loc + lcp);
        return pat1;
    }

    public static Interval maximizeToInterval(int[] pat, Interval inter,
            SuffixArray sa, SuffixArray pa,
            Store store) {
        Interval found = pa.revSearch(pat, inter);
        int lcp = pa.getLcp(found);
        int loc = pa.suftab[found.lb()];
        int[] pat1 = store.toArray(loc - lcp + 1, loc + 1);
        return sa.search(pat1, inter);
    }

    public static boolean isMaximal(int[] pat, Interval inter,
            SuffixArray sa, SuffixArray pa,
            Store store) {

        Interval found = pa.revSearch(pat, inter);
        if (found.trivial()) {
            return false;
        }
        int lcp = pa.getLcp(found);
        int loc = pa.suftab[found.lb()];
        int[] pat1 = store.toArray(loc - lcp + 1, loc + 1);
        if (pat1.length > pat.length) {
            return false;
        }
        found = sa.search(pat1, inter);
        lcp = sa.getLcp(found);
        loc = sa.suftab[found.lb()];
        pat1 = store.toArray(loc, loc + lcp);
        if (pat1.length > pat.length) {
            return false;
        }
        return true;
    }

    /**
     * Reverse search. To be used when this SuffixArray is actually encoding a
     * prefix array.
     *
     * @param pat the pattern to look for
     * @return the Interval where the pattern is found. A search miss returns a
     * null interval. See the <code>before</code> and <code>after</code> methods
     * in {@link Interval}.
     */
    public Interval revSearch(int[] pat) {
        return revSearch(pat, pat.length - 1, top);
    }

    /**
     * Reverse search. To be used when this SuffixArray is actually encoding a
     * prefix array.
     *
     * @param pat the pattern to look for
     * @param inter the Interval in which to look.
     * @return the Interval where the pattern is found. A search miss returns a
     * null interval. See the <code>before</code> and <code>after</code> methods
     * in {@link Interval}.
     */
    public Interval revSearch(int[] pat, Interval inter) {
        return revSearch(pat, pat.length - 1, inter);
    }

    Interval revSearch(int[] pat, int i, Interval inter) {
        if (inter.trivial()) {
            int p = suftab[inter.lb()];

            for (; i >= 0 && p - (pat.length - 1 - i) > 0; i--) {

                //niko. int pos = (p - (pat.length - 1 - i)); // unused
                // System.out.println( "In text: "+store.toString(pos,pos+1));

                int c = text[p - (pat.length - 1 - i)];
                // System.out.println("in pattern: "+store.toString(c));


                if (pat[i] < c) {
                    return inter.before();
                } else if (pat[i] > c) {
                    return inter.after();
                }
            }
            return inter;
        }
        // Get child boundary
        int mid = cldtab[inter.lb()];
        if (mid <= inter.lb() || mid > inter.rb()) {
            mid = cldtab[inter.rb()];
        }

        // Consume pattern up to the next lcp level. For non-leaves,
        // nothing happens here.
        for (; (pat.length - 1 - i) < lcptab[mid] && (1 + i) > 0; i--) {
            int c = text[suftab[mid] - (pat.length - 1 - i)];
            if (pat[i] < c) {
                return inter.before();
            } else if (pat[i] > c) {
                return inter.after();
            }
        }

        // After consuming from pattern, check to see if any remaining
        if (i == -1) {
            return inter;
        }

        // Decide left or right subtree
        Interval inter1;
        if (pat[i] < text[suftab[mid] - (pat.length - 1 - i)]) {
            inter1 = new Interval(inter.lb(), mid - 1);
        } else {
            inter1 = new Interval(mid, inter.rb());
        }

        // Niko. Throws stack overflow exception. 
        // Increase stack size here!
        return revSearch(pat, i, inter1);
    }

    /**
     * Reverse search. To be used when this SuffixArray is actually encoding a
     * prefix array.
     *
     * @param pat the pattern to look for
     * @return the Interval where the pattern is found. A search miss returns a
     * null interval. See the <code>before</code> and <code>after</code> methods
     * in {@link Interval}.
     */
    /**
     * Reverse search. To be used when this SuffixArray is actually encoding a
     * prefix array.
     *
     * @param pat the pattern to look for
     * @param inter the Interval in which to look.
     * @return the Interval where the pattern is found. A search miss returns a
     * null interval. See the <code>before</code> and <code>after</code> methods
     * in {@link Interval}.
     */
    ////
    public List<IntervalLink> pathToInterval(Interval inter, Interval top,
            int dir) {
        List<IntervalLink> result = new ArrayList<IntervalLink>();
        Interval prev = top;
        int prevLcp = 0;
        Interval current = null;
        while (true) {

            int mid = getMidPoint(prev);
            Interval c1 = new Interval(prev.lb(), mid - 1);
            Interval c2 = new Interval(mid, prev.rb());
            if (c1.contains(inter)) {
                current = c1;
            } else if (c2.contains(inter)) {
                current = c2;
            } else {
                return result;
            }

            int lcp = getLcp(current);
            int[] label = new int[lcp - prevLcp];
            for (int i = prevLcp, k = 0; i < lcp; i++, k++) {
                label[k] = text[suftab[current.lb()] + dir * i];
            }
            result.add(new IntervalLink(prev, current, label));
            if (current.equals(prev)) {
                return result;
            }
            prev = current;
            prevLcp = lcp;
        }
    }

    /**
     * Reverse search path. To be used when this SuffixArray is actually
     * encoding a prefix array.
     *
     * @param pat the pattern to look for
     * @param inter the Interval in which to look.
     * @return the sequence of Interval encountered in the search
     */
    public List<Interval> revSearchPath(int[] pat, Interval inter) {
        List<Interval> result = new ArrayList<Interval>();
        result.add(inter);
        revSearchPath(pat, pat.length - 1, inter, result);
        return result;
    }

    void revSearchPath(int[] pat, int i, Interval inter, List<Interval> result) {
        if (inter.trivial()) {
            int p = suftab[inter.lb()];
            for (; i > -1 && p - (pat.length - 1 - i) > 0; i--) {
                int c = text[p - (pat.length - 1 - i)];

                if (pat[i] < c) {
                    result.add(inter.before());
                    return;
                } else if (pat[i] > c) {
                    result.add(inter.after());
                    return;
                }
            }
            result.add(inter);
            return;
        }


        // Get child boundary
        int mid = cldtab[inter.lb()];
        if (mid <= inter.lb() || mid > inter.rb()) {
            mid = cldtab[inter.rb()];
        }

        // Consume pattern up to the next lcp level. For non-leaves,
        // nothing happens here.
        int level = i;
        for (; (pat.length - 1 - i) < lcptab[mid] && (1 + i) > 0; i--) {
            int c = text[suftab[mid] - (pat.length - 1 - i)];
            if (pat[i] < c) {
                result.add(inter.before());
                return;
            } else if (pat[i] > c) {
                result.add(inter.after());
                return;
            }
        }


        if (level != i) {
            result.add(inter);
        }

        // After consuming from pattern, check to see if any remaining
        if (i == -1) {
            return;
        }

        // Decide left or right subtree
        Interval inter1;
        if (pat[i] < text[suftab[mid] - (pat.length - 1 - i)]) {
            inter1 = new Interval(inter.lb(), mid - 1);
        } else {
            inter1 = new Interval(mid, inter.rb());
        }

        revSearchPath(pat, i, inter1, result);
    }

    /**
     * @return the text
     */
    public int[] getText() {
        return text;
    }

    /**
     * @return the sorted array of suffixes
     */
    public int[] getSuftab() {
        return suftab;
    }

    /**
     * @return the lcp table
     */
    public int[] getLcptab() {
        return lcptab;
    }

    
   
    
    /**
     * @return the child table
     */
    public int[] getCldtab() {
        return cldtab;
    }

    // alternative syntax for the above
    public int[] getChildTable() {
        return cldtab;
    }

    /**
     * Get lcp of an assumed-to-be-valid interval. Function described on p. 71
     * Abouelhoda
     *
     * @param inter the Interval
     * @return the lcp (longest common prefix)
     */
    public int getLcp(Interval inter) {
        int i = inter.lb();
        int j = inter.rb();
        int mid = cldtab[j];
        if (i < mid && mid <= j) {
            return lcptab[mid];
        } else {
            return lcptab[cldtab[i]];
        }
    }

    /**
     * Sligtly more efficient method to get lcp when midpoint is known
     */
    public int getLcp(int mid) {
        return lcptab[cldtab[mid]];
    }

    /*
     * public int getLcp(DirectedInterval dInter) { return
     * getLcp(dInter.asUndirectedInterval()); }
     */
    /**
     * Get the mid point of an interval. This is very similar to the method:
     * getLcp.
     */
    public int getMidPoint(Interval inter) {
        //        System.err.println( interval);
        int i = inter.lb();
        int j = inter.rb();
        int mid = cldtab[j];
        if (i < mid && mid <= j) {
            return mid;
        } else {
            return cldtab[i];
        }
    }

    // Is the interval (lb,whatever) the last one in the linked list
    // of children. Only useful in Abouelhoda et al's approach. In Kim
    // et al's approach, there are always just two children, so it is
    // clear which one is last.
    static boolean last(int lb, int[] cldtab, int[] lcptab) {
        return lcptab[lb] != lcptab[cldtab[lb]];
    }
    // An empty list of intervals. Used for the children of a leaf.
    private static List<Interval> empty = new ArrayList<Interval>();

    // Get children of an interval. This isn't used anywhere, but it
    // could be useful. Perhaps it could be made public.
    List<Interval> getChildren(Interval inter) {
        return getChildren(inter, cldtab, lcptab);
    }

    static List<Interval> getChildren(Interval inter, int[] cldtab, int[] lcptab) {

        int lb = inter.lb();
        int rb = inter.rb();
        if (lb == rb) {
            return empty;
        }
        List<Interval> result = new ArrayList<Interval>();
        int lbi;

        if (lb < cldtab[rb] && cldtab[rb] <= rb) {
            lbi = cldtab[rb];
        } else {
            lbi = cldtab[lb];
        }
        result.add(new Interval(lb, lbi - 1));
        while (lbi < rb && !last(lbi, cldtab, lcptab)) {
            int rbi = cldtab[lbi];
            result.add(new Interval(lbi, rbi - 1));
            lbi = rbi;
        }
        result.add(new Interval(lbi, rb));
        return result;
    }

    // Like getChildren (as in Abouelhoda et al) but specialized to
    // the binary case. This isn't used anywhere, but it could be
    // useful. Perhaps it could be made public.
    List<Interval> getBinaryChildren(Interval inter) {
        return getBinaryChildren(inter, cldtab, lcptab);
    }

    static List<Interval> getBinaryChildren(Interval inter, int[] cldtab, int[] lcptab) {

        int lb = inter.lb();
        int rb = inter.rb();
        if (lb == rb) {
            return empty;
        }
        List<Interval> result = new ArrayList<Interval>();
        int lbi;

        if (lb < cldtab[rb] && cldtab[rb] <= rb) {
            lbi = cldtab[rb];
        } else {
            lbi = cldtab[lb];
        }
        result.add(new Interval(lb, lbi - 1));
        result.add(new Interval(lbi, rb));
        return result;
    }

    /**
     * @return array of int 1..text.length-1. Only for printing debugging
     * tables.
     */
    public int[] getIndices() {
        int n = text.length;
        int[] result = new int[n];
        for (int i = 1; i < n; i++) {
            result[i] = i;
        }
        return result;
    }
    
    public Store getStore() {
        return this.store;
    }

    /**
     * Get the actual suffix array, i.e. the list of lexicographically sorted suffixes.
     * @param text
     * @return
     */
    public static int[] getSuftab(int[] text) {

        boolean useRadixSort = true;

        if (useRadixSort) {
            int n = text.length;
            int[] result = new int[n];
            for (int i = 1; i < n; i++) {
                result[i] = i;
            }
            //System.out.print("\nUnsorted: "); for(int i : text) { System.out.print(i + "-"); } System.out.println();
            // Sort.
            RadixQSort.store = store;
            RadixQSort rx = new RadixQSort(text, store);
            //Stopwatch swRadixQSort = new Stopwatch();
            //System.out.println(result.length + "<-unsorted--");
            rx.sort(result);
            //System.out.println("Time for sorting (RadixQSort): " + swRadixQSort.elapsedTime());
            //System.out.print("Sorted: " ); for(int i : result) { System.out.print(i + "-");  } System.out.println();
            //System.out.println(result.length + "<-sorted--");
            return result;
        } 
        
        //////***//////
        //////***//////
        // Alternative sorting algorithm!
        // Skew sort.
        // TODO: Fix bug for multiple documents (cf. stuttgart 21 stems).
        // TODO: Compare to suftabs ---> radixqsort vs. dc3-skewsort.
        // and see if there is a difference.
        else {

            int[] toSort = new int[text.length + 3];
            System.arraycopy(text, 0, toSort, 0, text.length);
            // Append three zeros.
            toSort[text.length] = 0;
            toSort[text.length + 1] = 0;
            toSort[text.length + 2] = 0;
            //System.out.print("\nUnsorted: "); for(int i : toSort) { System.out.print(i + " "); } System.out.println();
            //System.out.println(text.length + "<-unsorted--");
            SkewSort dc3 = new SkewSort();
            int[] result = dc3.skewSort(toSort);
            //System.out.print("Sorted: "); for(int i : result) { System.out.print(i + "-"); } System.out.println();
            //System.out.println(result.length + "<-sorted--");
            return result;

        }
    }

    public void sortSparseSuftab(int[] subset) {

        RadixQSort.store = store;
        RadixQSort rx = new RadixQSort(store.text);
        rx.sort(subset, 0, subset.length - 1, 0);
    }

    // Precondition: i and j are indices into text and i != j
    static int lcp(int i, int j, int[] text) {
        int result = 0;
        // Eventually there will be a mismatch since sentinels are unique
        while (text[i++] == text[j++] && !tc.userSentinel(text[i - 1])) {
            result++;
        }
        return result;
    }

    /**
     * Naive algorithm for getting lcp array. Lcp table construction is
     * performed by the constructor, so the average user has little need for
     * this method.
     *
     * @param suftab the sorted suffix table
     * @param text the tokenized text with strings replaced by integers
     * @return the lcp array
     */
    public static int[] getLcptab(int[] suftab, int[] text) {

        int[] result = new int[suftab.length];

        result[1] = -1;
        for (int i = 2; i < suftab.length; i++) {
            result[i] = lcp(suftab[i], suftab[i - 1], text);

        }
        return result;
    }
    
    /**
     * Get lcp tab with explicit boundary symbols.
     * @param suftab
     * @param text
     * @param tc
     * @return 
     */
    public static int[] getLcptab(int[] suftab, int[] text, BoundarySymbols tc) {

        int[] result = new int[suftab.length];

        result[1] = -1;
        for (int i = 2; i < suftab.length; i++) {
            result[i] = lcp(suftab[i], suftab[i - 1], text, tc);

        }
        return result;
    }
    private static int lcp(int i, int j, int[] text, BoundarySymbols tc) {
        int result = 0;
        // Eventually there will be a mismatch since sentinels are unique
        while (text[i++] == text[j++] && !tc.userSentinel(text[i - 1])) {
            result++;
        }
        return result;
    }
    // ***
    

    /**
     * Kasai et al algorithm for getting lcp array. Lcp table construction is
     * performed by the constructor, so the average user has little need for
     * this method.
     *
     * @param suftab the sorted suffix table
     * @param text the tokenized text with strings replaced by integers
     * @return the lcp array
     */
    public static int[] getLcpArrKasai(int[] suftab, int[] text) {
        int n = suftab.length - 1;
        int[] lcp = new int[n + 1];
        int[] rank = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            rank[suftab[i]] = i;
        }
        int h = 0;
        for (int i = 1; i <= n; i++) {
            int k = rank[i];
            if (k == 1) {
                lcp[k] = -1;
            } else {
                int j = suftab[k - 1];
                while (i + h <= n && j + h <= n && text[i + h] == text[j + h]) {
                    h++;
                }
                lcp[k] = h;
            }
            if (h > 0) {
                h--;
            }
        }
        return lcp;
    }

    /**
     * Get the Burrows-Wheeler table. This table is not constructed by default,
     * so the method is made public in case a user needs such table. This table
     * is discussed in Abouelhoda.
     *
     * @param suftab the sorted suffix table
     * @param text the tokenized text with strings replaced by integers
     * @return the Burrows Wheeler table
     */
    public static int[] getBwttab(int[] suftab, int[] text) {
        int[] result = new int[suftab.length];
        for (int i = 1; i < suftab.length; i++) {
            if (suftab[i] == 0) {
                result[i] = -1;
            } else {
                result[i] = text[suftab[i] - 1];
            }
        }
        return result;
    }

    // This method is used to get both the old and the new child
    // table. The only difference is that lcp table.
    static int[] getChildtab(int[] lcptab) {

        int n = lcptab.length - 1;
        int[] cldtab = new int[n + 1];
        Stack<Integer> stack = new Stack<Integer>();

        // The CHILD procedure
        stack.push(1);
        int lastIndex = -1;
        for (int i = 2; i <= n; i++) {
            // System.out.println(stack);
            while (lcptab[i] < lcptab[stack.peek()]) {
                
                lastIndex = stack.pop();
                int p = -3;
                try {
                    p = stack.peek();
                } catch (Exception e) {
                    System.out.println("Child procedure exception!");
                    System.out.println(e.getStackTrace());
                    System.out.println(e.getMessage());
                    System.out.println(store.docNameOfPos(suftab1[i]));
                    System.exit(0);
                }
                if (lcptab[i] < lcptab[stack.peek()]
                        && lcptab[stack.peek()] != lcptab[lastIndex]) {
                    cldtab[stack.peek()] = lastIndex;
                }
            }
            if (lastIndex != -1) {
                cldtab[i - 1] = lastIndex;
                lastIndex = -1;
            }
            stack.push(i);
        }

        // Kim et al say that lcptab should be padded with a sentinel
        // value: -2. The following has the same effect and avoids
        // having to modify lcptab.
        lastIndex = stack.pop();
        while (!stack.isEmpty()) {
            if (lcptab[stack.peek()] != lcptab[lastIndex]) {
                cldtab[stack.peek()] = lastIndex;
            }
            lastIndex = stack.pop();
        }

        cldtab[n] = lastIndex;

        // The NEXT procedure
        stack.push(1);
        for (int i = 2; i <= n; i++) {
            while (lcptab[i] < lcptab[stack.peek()]) {
                stack.pop();
            }
            if (lcptab[i] == lcptab[stack.peek()]) {
                lastIndex = stack.pop();
                cldtab[lastIndex] = i;
            }
            stack.push(i);
        }
        return cldtab;
    }

    public int getMaxLcp() {
        int maxLcp = 0;
        int maxLcpPos = 0;
        int pos = 0;
        for (int i : lcptab) {
            if (i > maxLcp) {
                maxLcp = i;
                maxLcpPos = pos;
            }
            pos++;
        }
        System.out.println(maxLcpPos);
        return maxLcp;
    }

    // Get the extended lcp table, which is used for constructing the
    // new child table.
    static int[] getExtlcp(int alphaSize, int[] cldtab, int[] lcptab) {
        int n = lcptab.length;
        Interval inter = new Interval(1, n - 1);
        int[] result = new int[n];
        traverseDepths(inter, result, alphaSize, cldtab, lcptab);
        return result;
    }

    // See method above.
    static void traverseDepths(Interval top, int[] result, int alphaSize,
            int[] cldtab, int[] lcptab) {
        List<Interval> children = getChildren(top, cldtab, lcptab);

        int n = children.size();

        for (int i = 1; i < n; i++) {
            Interval child = children.get(i);
            result[child.lb()] = lcptab[child.lb()] * alphaSize
                    + depth(i + 1, n);
        }
        for (Interval child : children) {
            traverseDepths(child, result, alphaSize, cldtab, lcptab);
        }
    }

    /**
     * Ceiling of base 2 log
     */
    public static int ceillog(int n) {
        assert (n >= 1);
        int c = 0;
        while (Math.pow(2, c) < n) {
            c++;
        }
        return c;
    }

    /**
     * The floor of the base 2 log. Could also be defined as: (int)
     * Math.floor(Math.log(x)/Math.log(2));
     * <p/>
     * Or, could also be defined as:
     * <p/>
     * static int floorlog(int n) { int c; for (c = 0; Math.pow(2,c) <= n; c++)
     * {} return c-1; }
     */
    public static int floorlog(int n) {
        int d = 0;
        while (n != 1) {
            n /= 2;
            d++;
        }
        return d;
    }

    /**
     * @return the number of trailing zeros in binary representation
     */
    public static int ntz(int n) {
        int r = 0;
        while ((1 & n >> r) == 0) {
            r++;
        }
        return r;
    }

    // Discussed in Kim et al. Used for calculating position of a node
    // k in a complete binary tree of size n. This code is currently
    // disabled, as it has been replaced by the code below. The new
    // code is faster, but mainly it has the advantage of being my own
    // invention.
    public static int xdepth(int k, int n) {
        int d = floorlog(n);
        int k1 = n - (int) Math.pow(2, d);
        if (k <= 2 * k1) {
            d++;
        } else {
            k -= k1;
        }
        return d - ntz(k - 1) - 1;
    }
    // www.research.att.com/~njas/sequences/A006165
    static List<Integer> a006165 = new ArrayList<Integer>();

    static {
        a006165.add(-1);
        a006165.add(1);
        a006165.add(1);
    }

    static int A006165(int n) {
        n += 2; // offset
        for (int i = a006165.size(); i <= n; i++) {
            if (i % 2 == 1) {
                a006165.add(a006165.get(i / 2) + a006165.get(i / 2 + 1));
            } else {
                a006165.add(2 * a006165.get(i / 2));
            }
        }
        return a006165.get(n);
    }

    // Is this really kind of like an average? How does it compare to
    // other averages?
    static int avg(int l, int r) {
        return A006165(r - l) + l - 1;
    }
    static int depthCacheSize = 89;  // very arbitrary choice
    static int[][] depthCache = new int[depthCacheSize][];

    static {
        for (int i = 2; i < depthCacheSize; i++) {
            depthCache[i] = ruler(i);
        }
    }

    static int[] ruler(int n) {
        int[] result = new int[n + 1];
        ruler(2, n, 0, result);
        return result;
    }

    public static void ruler(int l, int r, int d, int[] result) {
        if (l > r) {
            return;
        }
        int av = avg(l, r);
        ruler(l, av - 1, d + 1, result);
        result[av] = d;
        ruler(av + 1, r, d + 1, result);
    }

    public static int depth(int k, int n) {
        if (n < depthCacheSize) {
            return depthCache[n][k];
        }
        return rdepth(k, 2, n);
    }

    public static int rdepth(int k, int l, int n) {
        int av = avg(l, n);
        if (k == av) {
            return 0;
        }
        if (k < av) {
            return 1 + rdepth(k, l, av - 1);
        }
        return 1 + rdepth(k, av + 1, n);

    }

    public Interval[] getLnktab() {
        if (lnktab == null) {
            getSuffixLinks();
        }
        return lnktab;
    }

    public void getSuffixLinks() {

        CollectLevelIntervals collect =
                new CollectLevelIntervals(store, this, top);
        CollectTraversal p =
                new CollectTraversal(store, this, collect, top);
        p.traverse();
        lnktab = new Interval[N];
        List<List<Interval>> lList = collect.getlList();
        List<Set<LinkedInterval>> nList = collect.getnList();

        for (int i = 2; i < nList.size(); i++) {
            Set<LinkedInterval> nListRow =
                    nList.get(i);
            List<Interval> lListRow =
                    lList.get(i - 1);
            int li = 0;
            Interval candidate = lListRow.get(li);
            for (LinkedInterval psi : nListRow) {

                while (candidate.rb() < psi.inter.rb()) {
                    li++;
                    candidate = lListRow.get(li);
                }
                //System.out.println( "cand "+candidate);
                lnktab[psi.link] = candidate;
                while (candidate != null
                        && !candidate.leftVariation(getMidPoint(candidate), this,
                        store.text)) {
                    if (getLcp(candidate) > 1) {
                        candidate = lnktab[getMidPoint(candidate)];
                    } else {
                        candidate = null;
                        lnktab[psi.link] = null;
                    }
                }
            }
        }
    }

    /**
     * Test client.
     *
     * @param args
     */
    public static void main(String[] args) {
        String corpPath = "src/main/resources/corpusProjects/mining_engineering/";

        SaphreBase saphreBase =
                new SaphreBase(null, corpPath, corpPath + "/loadOptions/regex", corpPath + "/loadOptions/norm", corpPath + "/loadOptions/boundary", false, null).invoke();

        Store myStore = saphreBase.getStore();
        SuffixArray sa = saphreBase.getSa();
        SuffixArray pa = sa.prefixArray();
        
        

        int[] myText = saphreBase.getStore().text;
        
        // How to generate.
        //int[] mySuftab = SuffixArray.getSuftab(myText);
        //int[] myLcptab = SuffixArray.getLcptab(mySuftab, myText);
        
        // How to get.
        int[] mySuftab = sa.getSuftab();
        int[] myLcptab = sa.getLcptab();
        
        
        System.out.println("Text: " + Arrays.toString(myText));
        System.out.println("Suftab: " + Arrays.toString(mySuftab));
        System.out.println("Lcptab: " + Arrays.toString(myLcptab));

        // Remove sentinels.
        int[] realText = new int[myText.length - 3];
        System.arraycopy(myText, 2, realText, 0, myText.length - 3);
        int[] realSuftab = new int[myText.length - 3];
        System.arraycopy(mySuftab, 1, realSuftab, 0, myText.length - 3);
        int[] realLcptab = new int[myText.length - 3];
        System.arraycopy(myLcptab, 1, realLcptab, 0, myText.length - 3);

        System.out.println("Num tokens: " + store.numTokens());


        String n = "n";
        int toInt = myStore.toInt(n);
        int[] arr = new int[1];
        arr[0] = toInt;

        Interval resultingInterval = sa.search(arr);
        System.out.println("Interval: [" + resultingInterval.lb() + "-" + resultingInterval.rb() + "]");
        System.out.println("Term frequency: " + resultingInterval.tf());
        System.out.println("Document frequency: " + resultingInterval.df(saphreBase.getSa(), myStore));
        System.out.println("Maximal: " + SuffixArray.isMaximal(arr, sa.top, sa, pa, store));

    }
}
